package DP;

import java.util.Arrays;
import java.util.Map;

/**
 * @Classname JZ60n个骰子的点数
 * @Description TODO
 * @Date 2022/12/24 15:00
 * @Created by xjl
 */
public class JZ60n个骰子的点数 {

    public double[] dicesProbability(int n) {
        // 设置的n=1的时候的结果
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        // 当n>=2的时候
        for (int i = 2; i <= n; i++) {
            // 可能的出现的情况是有5 * i + 1种
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }

    public double[] dicesProbability2(int n) {
        StringBuilder stringBuilder=new StringBuilder();
        StringBuffer stringBuffer=new StringBuffer();
        // 表示的i个骰子的时候的等于j的和多少种情况 f(i,j)=f(i-1,j-1)+f(i-1,j-2)+……f(i-1,j-6)
        int[][] dp = new int[n + 1][6 * n + 1];
        // f(i,1)=1 f(1,2)=1 …… f(1,6)=1

        for (int i = 1; i <= 6; i++) {
            dp[1][i] = 1;
        }
        // i表示的i个骰子
        for (int i = 2; i <= n; i++) {
            // j 表示的和为j的情况
            for (int j = i; j <= 6 * i; j++) {
                // f(i,j)=f(i-1,j-1)+f(i-1,j-2)+……f(i-1,j-6)
                for (int k = 1; k <= 6; k++) {
                    if (j < k) {
                        break;
                    }
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }

        double[] res=new double[5*n+1];
        int index=0;
        double sum= Math.pow(6,n);
        // n 表示的n骰子的情况
        for (int i=n;i<=6*n;i++){
            res[index++]=dp[n][i]/sum;
        }
        return res;
    }
}
